package com.example.myletcodelearing.one

import java.util.*
import kotlin.collections.HashMap
import kotlin.math.abs


/**
 * @author tgw
 * @date 2022/11/7
https://leetcode.cn/problems/xoh6Oh/?favorite=e8X3pBZi

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

 

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
 

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/xoh6Oh
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

fun main(args: Array<String>) {
    var op = Solution16.Solution()

    var num = op.divide(-2147483648, 2)
    println("余数：$num")
}

private class Solution16 {
    class Solution {
        fun divide(a: Int, b: Int): Int {
            if (a == 0 || b == 0) {
                return 0
            }

            var mu: Long = Math.abs(a).toLong()
            var zi: Long = Math.abs(b).toLong()
            var add = (a > 0 && b > 0 || a < 0 && b < 0)
            if (mu > 2147483647) {
                mu = 2147483647.toLong()
            }
            if (mu <= -2147483648) {
                if (!add) {
                    mu = 2147483648L
                } else {
                    mu = 2147483647.toLong()

                }
            }
            var num: Long = zi
            var index: Long = 1
            while (num + zi <= mu) {
                num = num + zi
                index++
            }
            if (mu == zi) {
                index = 1
            } else if (index.toInt() == 1) {
                index = 0
            }

            if (!add) {
                index = 0 - index
            }
            return index.toInt()
        }
    }

    fun divide1(a: Int, b: Int): Int {
        var a = a
        var ans = 0 // 最终的商
        while (a >= b) {
            var d = b
            var c = 1 // 当前倍增的部分商
            while (d <= Int.MAX_VALUE shr 1 && d + d <= a) {
                d += d // 除数倍增
                c += c // 当前商倍增
            }
            a -= d // a剩余部分
            ans += c // 累计商
        }
        return ans
    }

}
